package sort

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

// 直接插入排序 是吧后一个元素去前面已经排序完成的区间内插入
func DirectInsertSort(num []int) []int {
	for i := 1; i < len(num); i++ {
		for j := i; j > 0 && num[j] < num[j-1]; j-- {
			num[j], num[j-1] = num[j-1], num[j]
		}
	}
	return num
}

func ShellSort(num []int, c int) []int {
	if c == 0 {
		return DirectInsertSort(num)
	}
	for i := c; i < len(num); i++ {
		if num[i] < num[i-c] {
			num[i], num[i-c] = num[i-c], num[i]
		}
	}
	return ShellSort(num, c/2)
}

// 最好情况是n*log(n), 最差情况是O(n*n)
// 使用分治法
func QuickSort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	index := rand.Intn(len(nums))
	pivot := nums[index]
	//fmt.Println(index, pivot)
	low := make([]int, 0, len(nums)/2)
	high:= make([]int, 0, len(nums)/2)
	for i , v := range nums {
		if i != index {
			if v > pivot {
				high = append(high, v)
			}else{
				low = append(low, v)
			}
		}
	}
	return append(append(QuickSort(low), pivot), QuickSort(high)...)
}

//这是自己想出来的一个TopK问题的解法，根据快排改变
//快排会分治，而TopK的数据则一定会在某一边
//就有两种种情况
//		1. topK全在一边，那就不用在对另一半排序
//		2. topK一部分在一边（这边全是topK的数据），另一部分在另一半， 而这又形成了一个topk的子问题
func QuickSortTopK(nums []int, topK int)[]int{
	if len(nums) < 2 {
		return nums
	}
	index := rand.Intn(len(nums))
	pivot := nums[index]
	low := make([]int, 0, len(nums)/2)
	high:= make([]int, 0, len(nums)/2)
	for i , v := range nums {
		if i != index {
			if v > pivot {
				high = append(high, v)
			}else{
				low = append(low, v)
			}
		}
	}
	fmt.Println(pivot, topK,high)
	if len(high) > topK {
		return QuickSortTopK(high, topK)
	}else if len(high) == topK {
		return QuickSort(high)
	}else{
		topK -= len(high)
		low = append(low, pivot)
		return append(QuickSort(high), QuickSortTopK(low, topK)...)
	}
	//return append(append(QuickSort(low), pivot), QuickSort(high)...)
}

// topk 的改进型，最好的情况就是O(1),恰好分到topk
//				 最坏的情况就是O(n^2), 平均是时间复杂度与快排相同
func QuickSortTopK2(nums []int, topK int)(high []int){
	fmt.Println("topk: ", topK)
	if topK == 0 {
		return []int{}
	}
	if len(nums) < 2 {
		return nums
	}
	rand.Seed(time.Now().UnixMilli())
	index := rand.Intn(len(nums))
	pivot := nums[index]
	low := make([]int, 0, len(nums)/2)
	high = make([]int, 0, len(nums)/2)
	for i , v := range nums {
		if i != index {
			if v > pivot {
				high = append(high, v)
			}else{
				low = append(low, v)
			}
		}
	}
	fmt.Println(pivot, topK,high)
	if len(high) > topK {
		// 最多 len(hight) - topk 次， 每次pivot的是最小的， O(n^2), 平均是时间复杂度与快排相同
		high = QuickSortTopK2(high, topK)
	}else if len(high) < topK {
		// 这种情况最多 topK 次 O(topK * log(n))
		topK -= len(high) + 1
		high = append(append(high, pivot), QuickSortTopK2(low, topK)...)
	}
	//return append(append(QuickSort(low), pivot), QuickSort(high)...)
	// 这个可以拿到外部排序
	sort.Ints(high)
	return high
}

// // 在此改性， 因为每次都有一次对当前数据集O(n)的遍历，
// // 除了在初次进入是不能求得平均数，
// // 以后的每一次都能知道平均数，保证每次pivot不是最大或最小
// func QuickSortTopK3(nums []int, topK int , curAvg int, isFirst bool)(high []int){
// 	fmt.Println("topk: ", topK)
// 	if topK == 0 {
// 		return []int{}
// 	}
// 	if len(nums) < 2 {
// 		return nums
// 	}
// 	// pivot 使用平均数来
// 	pivot := 0
// 	low := make([]int, 0, len(nums)/2)
// 	high = make([]int, 0, len(nums)/2)
// 	for _ , v := range nums {
// 		if v > pivot {
// 			high = append(high, v)
// 		}else{
// 			low = append(low, v)
// 		}
// 	}
// 	fmt.Println(pivot, topK,high)
// 	if len(high) > topK {
// 		// 最多 len(hight) - topk 次， 每次pivot的是最小的， O(n^2), 平均是时间复杂度与快排相同
// 		high = QuickSortTopK2(high, topK)
// 	}else if len(high) < topK {
// 		// 这种情况最多 topK 次 O(topK * log(n))
// 		topK -= len(high) + 1
// 		high = append(append(high, pivot), QuickSortTopK2(low, topK)...)
// 	}
// 	//return append(append(QuickSort(low), pivot), QuickSort(high)...)
// 	// 这个可以拿到外部排序
// 	sort.Ints(high)
// 	return high
// }


// 冒泡排序
// 是两两交换,把最值交换至头或尾
func BobSort(nums []int)[]int{
	//改进,如果本身数组有序,则不需要再进行后续的交换
	flag := true
	for i := 0 ; i < len(nums) && flag; i++ {
		//flag =false
		for j := 1 ; j < len(nums) - i ; j++ {
			if nums[j] < nums[j-1] {
				nums[j] , nums[j -1] = nums[j-1] , nums[j]
				flag = true
			}
		}
	}
	return nums
}